import collections
from typing import List


class Solution:
    def containVirus(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def _is_valid(x, y):
            return 0 <= x < m and 0 <= y < n

        # 四个方向传递
        def neighbors(x1, y1):
            return [(x2, y2) for (x2, y2) in [(x1 - 1, y1), (x1 + 1, y1), (x1, y1 - 1), (x1, y1 + 1)]
                    if _is_valid(x2, y2)]

        ans = 0

        total_control = set()  # 已被隔离的地区

        while True:
            # 计算每一块被感染的区域
            areas = []
            total_lost = set()  # 已被感染的位置
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 1 and (i, j) not in total_lost and (i, j) not in total_control:
                        area_lost = {(i, j)}  # 区域已感染位置
                        area_danger = set()  # 区域被威胁位置
                        area_need = 0  # 区域需要的防火墙
                        queue = collections.deque([(i, j)])
                        while queue:
                            i1, j1 = queue.popleft()
                            for i2, j2 in neighbors(i1, j1):
                                if grid[i2][j2] == 1 and (i2, j2) not in area_lost and (i2, j2) not in total_control:
                                    area_lost.add((i2, j2))
                                    queue.append((i2, j2))
                                elif grid[i2][j2] == 0:
                                    area_danger.add((i2, j2))
                                    area_need += 1
                        areas.append([area_lost, area_danger, area_need])
                        total_lost |= area_lost

            # 按每一块区域的威胁程度排序
            areas.sort(key=lambda x: len(x[1]), reverse=True)

            # 如果没有没被控制的感染区域
            if len(areas) == 0:
                return ans

            # 如果最大威胁程度为0，则说明已被全部感染
            if areas[0][2] == 0:
                return ans

            # 修建威胁最大区域的防火墙
            ans += areas[0][2]

            # 如果只有最后一块感染区
            if len(areas) == 1:
                return ans

            # 将当前区域添加到隔离区
            total_control |= areas[0][0]

            # 除隔离区外其他地区传染
            for area_lost, area_danger, area_need in areas[1:]:
                for i1, j1 in area_danger:
                    grid[i1][j1] = 1


if __name__ == "__main__":
    # 10
    print(Solution().containVirus(grid=
                                  [[0, 1, 0, 0, 0, 0, 0, 1],
                                   [0, 1, 0, 0, 0, 0, 0, 1],
                                   [0, 0, 0, 0, 0, 0, 0, 1],
                                   [0, 0, 0, 0, 0, 0, 0, 0]]))

    # 4
    print(Solution().containVirus(grid=
                                  [[1, 1, 1],
                                   [1, 0, 1],
                                   [1, 1, 1]]))

    # 13
    print(Solution().containVirus(grid=
                                  [[1, 1, 1, 0, 0, 0, 0, 0, 0],
                                   [1, 0, 1, 0, 1, 1, 1, 1, 1],
                                   [1, 1, 1, 0, 0, 0, 0, 0, 0]]))
